#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
  int m = obstacleGrid.size();
  int n=0;
  if(m>0)
  {
    n = obstacleGrid[0].size();
    if(n<1)
      return 0;
  }
  else
  {
    return 0;
  }
  //m>0&&n>0

  vector< vector<int> > ans;
  for(int i=0;i<m+1;++i)
  {
    ans.push_back( vector<int> (n+1,0) );     
  }
  ans[0][1]=1;

  for(int i=1;i<m+1;++i)
    for(int j=1;j<n+1;++j)
    {
      if( obstacleGrid[i-1][j-1] != 1 )
      {
        ans[i][j] = ans[i-1][j] + ans[i][j-1];
      }
      else
      {
        ans[i][j] = 0;
      }
    }

  return ans[m][n];
}



int main(int argc,char *argv[])
{
  vector< vector<int> > obj;
  obj.push_back(vector<int> {0,0,0});
  obj.push_back(vector<int> {0,1,0});
  obj.push_back(vector<int> {0,0,0});
  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  int ret = uniquePathsWithObstacles(obj);

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;

  cout<<"ret:"<<ret<<endl;

  return 0;
}
